#include <stdio.h>
#include <stdlib.h>
#include "test.h"
// 桶节点结构
struct Node {
    float data;
    struct Node* next;
};

// 插入排序（稳定）
struct Node* InsertionSort(struct Node* list) {
    if (!list || !list->next) return list;
    struct Node dummy = {0, NULL};
    struct Node *cur = list, *next;
    while (cur) {
        next = cur->next;
        struct Node *prev = &dummy;
        while (prev->next && prev->next->data <= cur->data){           // prev->next 表示新序列不为空。当前插入的和新序列逐个比阿较。 
            prev = prev->next;
        }
        cur->next = prev->next;
        prev->next = cur;
        cur = next;
    }
    return dummy.next;
}

// 桶排序主函数
void BucketSort(float arr[], int n) {
    // 1. 初始化桶
    struct Node **buckets = (struct Node**)malloc(10 * sizeof(struct Node*)); // 10个桶
    for (int i = 0; i < 10; i++) 
        buckets[i] = NULL;

    // 2. 分桶（假设数据在[0,1)区间）
    for (int i = 0; i < n; i++) {
        int bucket_idx = arr[i] * 10; // 映射到0-9的桶
        struct Node *new_node = (struct Node*)malloc(sizeof(struct Node));
        new_node->data = arr[i];
        new_node->next = buckets[bucket_idx];
        buckets[bucket_idx] = new_node;           //头插法。
    }

    // 3. 桶内排序并合并
    int idx = 0;
    for (int i = 0; i < 10; i++) {
        buckets[i] = InsertionSort(buckets[i]); // 对桶排序
        struct Node *cur = buckets[i];
        while (cur) {
            arr[idx++] = cur->data;
            struct Node *tmp = cur;
            cur = cur->next;
            free(tmp); // 释放节点
        }
    }
    free(buckets);
}

// 测试用例
int main() {
    float arr[] = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前: ");
    for (int i = 0; i < n; i++) printf("%.2f ", arr[i]);

    BucketSort(arr, n);

    printf("\n排序后: ");
    for (int i = 0; i < n; i++) printf("%.2f ", arr[i]);
    // 输出: 0.23 0.25 0.32 0.42 0.47 0.51 0.52



    //benchmark(BucketSort);
    return 0;
}

//通用写法
/*
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Node {
    float data;
    struct Node* next;
};

void insertSorted(struct Node** head, float value) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    
    if (*head == NULL || (*head)->data > value) {
        newNode->next = *head;
        *head = newNode;
    } else {
        struct Node* current = *head;
        while (current->next && current->next->data < value) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

void bucketSort_Standard(float arr[], int n) {
    // 假设数据在 [0, 1) 范围内
    int bucketCount = n;
    struct Node** buckets = malloc(bucketCount * sizeof(struct Node*));
    
    // 初始化桶
    for (int i = 0; i < bucketCount; i++) {
        buckets[i] = NULL;
    }
    
    // 分配元素到桶
    for (int i = 0; i < n; i++) {
        int bucketIndex = (int)(bucketCount * arr[i]);
        if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;
        insertSorted(&buckets[bucketIndex], arr[i]);
    }
    
    // 收集结果
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        struct Node* current = buckets[i];
        while (current) {
            arr[index++] = current->data;
            struct Node* temp = current;
            current = current->next;
            free(temp);
        }
    }
    
    free(buckets);
}

*/